import java.util.ArrayList;
import java.util.List;

class Solution23 {
    public List<List<String>> ret;
    public char[][] path;
    public boolean[] col;//判断列
    public boolean[] dig1;//判断主对角线
    public boolean[] dig2;//判断副对角线
    public List<List<String>> solveNQueens(int n) {
        path = new char[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                path[i][j] = '.';
            }
        }
        ret = new ArrayList<>();
        col = new boolean[n];
        dig1 = new boolean[2*n];
        dig2 = new boolean[2*n];
        dfs(n,0);
        return ret;
    }

    public void dfs(int n,int pos) {
        if(pos == n) {
            List<String> _path = new ArrayList<>();
            for(int i = 0; i < n; i++) {
                _path.add(new String(path[i]));
            }
            ret.add(_path);
            return;
        }
        //i是行
        for(int i = 0; i < n; i++) {
            if(col[i] == false && dig1[pos - i + n] == false && dig2[pos+i] == false) {
                path[pos][i] = 'Q';
                col[i] = dig1[pos - i + n] = dig2[pos+i] = true;
                dfs(n,pos+1);
                path[pos][i] = '.';
                col[i] = dig1[pos - i + n] = dig2[pos+i] = false;
            }
        }
    }
}